package shujia.day20;

/*
    int[][] arr = new int[A.length()+1][B.length()+1]
    情况1：如果i==0 && j==0, arr[i][j]=0
    情况2：如果i==0, arr[i][j] = j
    情况3：如果j==0, arr[i][j] = i
    情况4：如果word1.charAt(i) == word2.charAt(j), arr[i][j] = arr[i-1][j-1]
    情况5：其他情况，arr[i][j] = min(arr[i][j-1], arr[i-1][j], arr[i-1][j-1])+1
 */
public class Test6 {
    public static void main(String[] args) {
//        A = "horse", B = "ros"
        String s1 = "horse";
        String s2 = "ros";
        int num = minProcess(s1, s2);
        System.out.println("horse 转换成 ros 所需的最少 " + num + " 操作次数");
    }

    public static int minProcess(String a, String b) {
        int aLen = a.length();
        int bLen = b.length();

        a = "#" + a;
        b = "$" + b;
        int[][] arr = new int[aLen + 1][bLen + 1];

        for (int i = 0; i <= aLen; i++) {
            for (int j = 0; j <= bLen; j++) {
                if (i == 0 && j == 0) {
                    arr[i][j] = 0;
                } else if (i == 0) {
                    arr[i][j] = j;
                } else if (j == 0) {
                    arr[i][j] = i;
                } else if (a.charAt(i) == b.charAt(j)) {
                    arr[i][j] = arr[i - 1][j - 1];
                } else {
                    arr[i][j] = Math.min(arr[i][j - 1], Math.min(arr[i - 1][j], arr[i - 1][j - 1])) + 1;
                }
            }
        }

        return arr[aLen][bLen];


    }
}
